Electrical Engineering-Systems Dept.

סמינר מחלקתי

You are invited to attend a lecture by

Prof. Guy Even

(Electrical Engineering-Systems Dept., TAU)

on the subject:

Message-passing algorithms for packing and covering linear programs

Message-passing algorithms based on Belief-Propagation (BP) are successfully used for decoding error correcting codes, solving constraint satisfaction problems, and many other fields.  BP-based algorithms operate on graphs, called factor graphs, that are used to model the input. Although in many cases BP-based algorithms exhibit impressive empirical results, not much has been proved when the factor graphs have cycles.

This work deals with the special case of packing and covering Linear Programs (LPs) in which the the variables and the constraint matrix are over the natural numbers. In addition, the variables are upper bounded. We study the performance of the min-sum algorithm when applied to the corresponding factor graph models of these LPs.

We prove that if the LP has an optimal fractional solution, then for each fractional component, the value computed by the min-sum algorithm oscillates between a value less than the fraction and a value greater than the fraction.  This implies that the min-sum algorithm computes the optimal integral solution only if the LP has a unique integral optimal solution.

Our result unifies and extends recent results presented for the maximum weighted matching problem by [Sanghavi et al.,'2011] and [Bayati et al.'2011] and for the maximum independent set problem [Snaghavi et al.'2009]

Joint work with Nissim Halabi.